#include <vector>
#include <iostream>

using namespace std;

int helper(vector<int> array){
    if (array.size() == 30) {
        return 1;
    }
    int result = 0;
    vector<int> copy = array;
    copy.push_back(1);
    result += helper(copy);

    copy = array;

    if (copy.back() == 1) {
        copy.push_back(0);
        result += helper(copy);
    }
    return result;
}

int solution() {
    return helper({1}) + helper({0});
}

int main(int argc, char const *argv[])
{
    vector<int> array;
    helper(array);
    cout << solution() << endl;
    return 0;
}
